//
// Created by Administrator on 2021/6/15.
//
#include <iostream>

using namespace std;

/**
 * 实现int sqrt(int x)函数。
计算并返回x的平方根，其中x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
 * @param x
 * @return
 */
class Solution {
public:
    int mySqrt(int x) {
        int lhs = 0, rhs = x / 2, ans = -1;
        while (lhs <= rhs) {
            int mid = lhs + (rhs - lhs) / 2;
            if ((long long) mid * mid <= x) {
                ans = mid;
                lhs = mid + 1;
            } else rhs = mid - 1;
        }
        return ans;
    }
};

int main() {
    Solution sol;
    cout << sol.mySqrt(7) << endl;
    return 0;
}